package com.lry.basic.algorithm.graph;


public class CycleDetection {
    private UndirectedGraph graph;
    private boolean[] visited;
    private boolean hasCycle;

    public CycleDetection(UndirectedGraph graph){
        this.graph = graph;
        visited = new boolean[graph.vertexNum()];
        for(int v=0;v<graph.vertexNum();v++){
            if(!visited[v]){
                dfs(v,v);
            }
        }
    }
    public boolean isHasCycle(){
        return hasCycle;
    }
    private void dfs(int v,int parent){
        visited[v] = true;
        for(int w:graph.adj(v)) {
            if(!visited[w]){
                dfs(w,v);
            }else if(w!=parent){
                hasCycle = true;
            }
        }
    }


    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        CycleDetection graphDFS = new CycleDetection(graph);
        System.out.println(graphDFS.isHasCycle());
    }
}
